"""
# 选择排序的思想就是将未排序的列表分为有序区和无序区
    每次都将无序区的最小数据拿出来放在最前面
# 选择排序的时间复杂度是o(N2)
[3, 1, 4, 2, 5, 7, 6, 8]
[1,         3, 4, 2, 5, 7, 6, 8]
[1, 2,         4, 3, 5, 7, 6, 8]
[1, 2, 3,         4, 5, 7, 6, 8]
[1, 2, 3, 4,         5, 7, 6, 8]
[1, 2, 3, 4, 5,         7, 6, 8]
[1, 2, 3, 4, 5, 6,         7, 8]
[1, 2, 3, 4, 5, 6, 7,         8]
[1, 2, 3, 4, 5, 6, 7, 8        ]

"""


def select_sort(li: list):
    print(li)
    n = len(li)
    for i in range(n - 1):  # 要遍历多少次？遍历剩下最后一个的时候就是最大的数了
        min_index = i       # 最小元素是i
        for j in range(i, n):  # 每次从什么地方到什么地方
            if li[j] < li[min_index]:
                min_index = j
        li[i], li[min_index] = li[min_index], li[i]
        print(li)
    return li


def select_sort_simple(li: list):
    """
    生成了新列表
    remove和min都不是o1操作
    """
    res = []
    for i in range(len(li)):
        res.append(min(li))
        li.remove(min(li))
    return res


if __name__ == '__main__':
    alist = [3, 1, 4, 2, 5, 7, 6, 8]
    # res = select_sort_simple(alist)
    res = select_sort(alist)
    print(res)
